\documentclass[12pt,a4paper]{article}
\usepackage{xeCJK}
\usepackage{ctex}
\usepackage{booktabs}
\usepackage{makecell}
\usepackage{geometry}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{graphicx}
\usepackage{wrapfig}
\usepackage{abstract}
\usepackage{float}
\usepackage{algorithmicx}
\usepackage[ruled]{algorithm}
\usepackage{algpseudocode}
\usepackage{xcolor}
\usepackage{setspace}
\usepackage{color}
\usepackage{bm}
\usepackage{url}
\usepackage{cite}
\usepackage{array}
\usepackage{textcomp}
\usepackage{appendix}
\usepackage{listings}

\setstretch{1.2} 
\setlength{\parindent}{0.8cm}
\geometry{left=3cm,right=3cm,top=2.5cm,bottom=2.5cm}

\title{\vspace{-2cm} \textbf{第八次课堂作业}}

\author{邵柯欣 \\学号：3200103310 \\课程名称：数据科学的数学基础}

\date{\today}

\begin{document}
\maketitle
\section{证明$\forall s>0, A \in \mathbb{R}^{m*n} (m > n)$the Tikhonov regularized least square problem有唯一解}
Proof:\\
$$min_{x \in \mathbb{R}^n}\|Ax - b\|_2^2 + s\|x\|_2^2 $$
\begin{align}
  J(x) &= \|Ax - b\|_2^2 + s\|x\|_2^2 \notag \\
  &\iff (x^TA^T - b^T)(Ax - b) + sx^Tx \notag \\
  &\iff x^TA^TAx - 2x^TA^Tb + b^Tb + sx^Tx \notag
\end{align}
$$\dfrac{\partial J}{\partial x} = 2A^TAx - 2A^Tb + 2sx = 0 \iff x = (A^TA + s\mathbb{I})^{-1}A^Tb$$
$\because A^TA$是实矩阵\\
$\therefore (A^TA)^T = A^T(A^T)^T = A^TA$\\
$\therefore A^TA$是半正定的。\\
$\because $ 半正定矩阵加正定矩阵一定为正定矩阵。\\
$\therefore A^TA + s\mathbb{I}$可逆。\\
$\therefore$ 解$x = (A^TA + s\mathbb{I})^{-1}A^Tb$存在且唯一。
\section{证明问题$min_{x \in \mathbb{R}^n, \|x\|_2^2 \le t}L(x), min_{x \in \mathbb{R}^n}J(x), \forall s > 0$是等价的，存在$t>0$，使得问题$min_{x \in \mathbb{R}^n}J(x)$的解也是问题$min_{x \in \mathbb{R}^n, \|x\|_2^2 \le t}L(x)$的解}
\begin{equation}
  J(x) = \|Ax - b\|_2^2 + s\|x\|_2^2,
\end{equation}
\begin{equation}
  L(x) = \|Ax - b\|_2^2.
\end{equation}
$$\dfrac{\partial J}{\partial x} = (2A^TA + 2s\mathbb{I})x - 2A^Tb$$
$$\dfrac{\partial L}{\partial x} = 2A^TAx - 2A^Tb$$
当$t = \|(A^TA + s\mathbb{I})^{-1}A^Tb\|_2^2$时，\\
问题$min_{x \in \mathbb{R}^n}J(x)$的解也是问题$min_{x \in \mathbb{R}^n, \|x\|_2^2 \le t}L(x)$的解。
\section{应用匹配追踪算法解决LASSO问题（仅进行两次迭代）}
Solution:\\
$$min_{x \in \mathbb{R}^n}\|Ax - b\|_2^2 + s\|x\|_1, s = 0.5$$
\[
A =
\begin{bmatrix}
  2 & 1 & -2\\
  1 & -1 & 1\\
\end{bmatrix},
r = b =
\begin{bmatrix}
  1\\
  3\\
\end{bmatrix},
X =
\begin{bmatrix}
  0\\
  0\\
  0\\
\end{bmatrix}
\]
\bf{for i = 1:}\\
\begin{align}
  \because \quad &|<r, A_1>| = 5, |<r, A_2>| = 2, |<r, A_3>| = 1.\notag\\
  \therefore \quad &A_1 = max_{A_j \in A}|<r, A_j>|;\notag\\
  and \quad &X_1 = \dfrac{1}{\|A_1\|_2^2}(<r, A_1> - \dfrac{s}{2}) = \dfrac{19}{20}; \notag
\end{align}
\[
r = r - A_1X_1 =
\begin{bmatrix}
  -\frac{11}{10}\\
  \frac{39}{10}\\
\end{bmatrix},
X =
\begin{bmatrix}
  \frac{19}{20}\\
  0\\
  0\\
\end{bmatrix}.
\]
\bf{for i = 2:}\\
\begin{align}
  \because \quad &|<r, A_1>| = dfrac{1}{4}, |<r, A_2>| = -\dfrac{59}{20}, |<r, A_3>| = \dfrac{77}{20}.\notag\\
  \therefore \quad &A_3 = max_{A_j \in A}|<r, A_j>|;\notag\\
  and \quad &X_3 = \dfrac{1}{\|A_3\|_2^2}(<r, A_3> - \dfrac{s}{2}) = \dfrac{18}{25}; \notag
\end{align}
\[
r = r - A_3X_3 =
\begin{bmatrix}
  -\frac{27}{50}\\
  \frac{133}{100}\\
\end{bmatrix},
X =
\begin{bmatrix}
  \frac{19}{20}\\
  0\\
  \frac{18}{25}\\
\end{bmatrix}.
\]
\end{document}
